package com.leetcode.algorithm.y18.m05;

/**
 * leetcode-cn.com
 * 680. 验证回文字符串 Ⅱ
 * 686. 重复叠加字符串匹配
 * @author dengjie213@126.com
 * 2018年5月20日 下午9:13:48
 */
public class MySolution0520 {
	
	/**
	 * 680. 验证回文字符串 Ⅱ
	 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
	 * 
	 * 示例 1:
	 * 输入: "aba" 
	 * 输出: True 
	 * 
	 * 示例 2:
	 * 输入: "abca" 输出: True 
	 * 解释: 你可以删除c字符。 
	 * 
	 * 注意:
	 * 字符串只包含从 a-z 的小写字母。
	 * 字符串的最大长度是50000。
	 * 
	 * @param s
	 * @return
	 */
	public boolean validPalindrome(String s) {
		char[] chars = s.toCharArray();
		int len = chars.length;
		int i = 0;
		int j = len - 1;
		while (i < j && chars[i] == chars[j]) {
			i++;
			j--;
		}
		if (i >= j) {
			return true;
		} else {
			// 删除左边的字符,验证剩下的字符是否回文串
			int left = i + 1, right = j;
			while (left < right && chars[left] == chars[right]) {
				left++;
				right--;
			}			
			if (left >= right) {
				return true;
			}
			// 删除右边的字符,验证剩下的字符是否回文串(删除左边的字符,不是回文串)
			left = i;
			right = j - 1;
			for (; left < right;) {
				if (chars[left] == chars[right]) {
					left++;
					right--;
				} else {
					return false;
				}
			}
			return true;
		}
	}
    
    /**
	 * 686. 重复叠加字符串匹配 
	 * 给定两个字符串 A 和 B, 寻找重复叠加字符串A的最小次数，使得字符串B成为叠加后的字符串A的子串，如果不存在则返回-1。
	 * 
	 * 举个例子，A = "abcd"，B = "cdabcdab"。
	 * 答案为 3， 因为 A 重复叠加三遍后为 “abcdabcdabcd”，此时 B 是其子串；A 重复叠加两遍后为"abcdabcd"，B 并不是其子串。
	 * 
	 * 注意:
	 * A 与 B 字符串的长度在1和10000区间范围内。
	 * 
	 * @param A
	 * @param B
	 * @return
	 */
	public int repeatedStringMatch(String A, String B) {
		int count = 0;
		if (A.indexOf(B) > -1) {
			return 1;
		} else {
			if((A+A).indexOf(B) > -1){
				return 2;
			}
			int fromIdx = B.indexOf(A);
			if (fromIdx == -1) {
				return -1;
			}
			int lenA = A.length();
			int lenB = B.length();
			if (fromIdx != 0) {
				if (A.endsWith(B.substring(0, fromIdx))) {
					count++;
				} else {
					return -1;
				}
			}
			int i = fromIdx;
			for (; i + lenA <= lenB;) {
				if (A.equals(B.substring(i, i + lenA))) {
					count++;
					i += lenA;
				} else {
					return -1;
				}
			}
			if (i < lenB) {
				if (A.startsWith(B.substring(i))) {
					count++;
				} else {
					return -1;
				}
			}
		}
		return count;
	}
    
}
